package leetcode.array;

/**
 * @author Cheng Jun
 * Description: 二分查找  升序数组中查找目标值 target
 * https://leetcode-cn.com/problems/binary-search/
 * @version 1.0
 * @date 2022/1/8 10:06 经典题 常出现于校招
 */
public class search {

  public static void main(String[] args) {
    search(new int[] {-1, 0, 3, 5, 9, 12}, 2);
  }

  /**
   * 第一次的做法，推荐使用模块1或模板2
   *
   * @author Cheng Jun
   * @date 2022/7/18 10:19
   * @param nums
   * @param target
   * @return int
   */
  @Deprecated
  public static int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
      // 注意这里，不要使用（left +  right）/ 2 去求mid，因为left + right 有可能超过int类型的最大值
      int mid = left + (right - left) / 2;
      if (nums[mid] == target) {
        return mid;
      } else if (target < nums[mid]) {
        // 注意这里的 减1，因为 nums[mid] 已经不符合要求
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return -1;
  }

  /**
   * 二分查找模板1，区间划分 [left, mid] [mid+1, right] mid = (left + right) / 2
   *
   * @author Cheng Jun
   * @date 2022/7/18 10:26
   * @param nums
   * @param target
   * @return int
   */
  static int search1(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
      int mid = left + (right - left) / 2;
      // int mid = (left + right) / 2;
      if (target == nums[mid]) {
        return mid;
      } else if (target < nums[mid]) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return nums[right] == target ? right : -1;
  }

  /**
   * 二分查找模板2，区间划分 [left, mid-1] [mid, right] mid = (left + right + 1) / 2
   *
   * @author Cheng Jun
   * @date 2022/7/18 10:27
   * @param nums
   * @param target
   * @return int
   */
  static int search2(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
      int mid = left + (right - left + 1) / 2;
      // int mid = (left + right + 1) / 2;
      if (target == nums[mid]) {
        return mid;
      } else if (target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid;
      }
    }
    return nums[right] == target ? right : -1;
  }
}
